package binary_tree.Heap.leetcode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Description: 找出数组中最小的k个数
 * @Author Stark
 * @Date 2022/3/6 15:59
 **/
public class Num17_14_SmallestKNum {
    public int[] smallestK(int[] arr, int k) {
        //若取出的k为0,返回空数组
        int[] ret = new int[0];
        if(k == 0){
            return ret;
        }
        //默认堆是小堆,变为大堆
        Queue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);
        //将数组前k个数直接如堆
        for(int i = 0; i < k;i++){
            queue.offer(arr[i]);
        }
        //队首元素和数组进行比较,比堆顶小的入堆
        for(int i = k; i < arr.length;i++){
            if(arr[i] < queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }
}
